# 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。 
# 
#  k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。 
# 
#  你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。 
# 
#  
# 
#  示例 1： 
#  
#  
# 输入：head = [1,2,3,4,5], k = 2
# 输出：[2,1,4,3,5]
#  
# 
#  示例 2： 
# 
#  
# 
#  
# 输入：head = [1,2,3,4,5], k = 3
# 输出：[3,2,1,4,5]
#  
# 
#  
# 提示：
# 
#  
#  链表中的节点数目为 n 
#  1 <= k <= n <= 5000 
#  0 <= Node.val <= 1000 
#  
# 
#  
# 
#  进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？ 
# 
#  
#  
# 
#  Related Topics 递归 链表 👍 2462 👎 0
from typing import Optional, List, Any, Tuple

from LeetCode.Test.LinkTool import ListNode, Link, LinkedListTool


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    """
    思路：1，将链子每k个一组断开，把数组翻转后的数组和最后一个node节点放入re数组
         2,将re里的链表连起来
    """
    """
    def reverseKGroup(self, head: Optional[ListNode], k: int):
        

        :param head:
        :param k:
        :return:

        re = []
        size = 1
        s = head
        while s.next:
            size += 1
            s = s.next

        cur = head
        for _ in range(size // k):
            root = cur
            for i in range(k - 1):
                cur = cur.next
            start_node = cur.next
            cur.next = None
            re.append(self.reverse(root))
            cur = start_node
        # 如果还有剩下的直接加入数组
        if cur:
            re.append([cur, None])

        for i in range(1, len(re)):
            # 将单独的链表串起来
            re[i - 1][1].next = re[i][0]
        return re[0][0]

    def reverse(self, head):

           返回翻转后的数组和最后一个node节点

        if not head:
            return head
        pre = None
        tail = head
        while True:
            next_node = head.next
            head.next = pre
            pre = head
            if not next_node:
                newhead = head
                return [newhead, tail]
            head = next_node
        """

    # 在本题目中。reverse的链表是从根节点开始，k个一组翻转。
    # 例如[1,2,3,4,5]翻转[2,3,4],需要考虑1要连接4，但在本题中不用考虑这个问题，因为翻转的链表是从head开始的，前面没有节点
    def reverse(self, head, tail) -> tuple[ListNode, ListNode] | Any:

        if not head:
            return head
        nex = tail.next
        curr = head
        while nex != tail:
            next_node = curr.next
            curr.next = nex
            nex = curr
            curr = next_node
        newhead, newtail = tail, head
        # 返回新链表的头 尾巴
        return newhead, newtail

    def reverseKGroup(self, head: Optional[ListNode], k: int):
        if k==1:
            return head
        dummy = ListNode(0)
        dummy.next = head
        pre = dummy
        while head:
            tail = pre
            # 检查剩下的节点还够k个?
            for _ in range(k):
                tail = tail.next
                if not tail:
                    return dummy.next

            next_head = tail.next
            # 翻转节点
            head, tail = self.reverse(head, tail)

            #接回原数组
            pre.next = head
            tail.next = next_head
            # 移动指针
            pre = tail
            head = next_head

# leetcode submit region end(Prohibit modification and deletion)
l = Solution().reverseKGroup(LinkedListTool([1, 2, 3, 4, 5]), 2)
Link.each(l)
# link = LinkedListTool([1, 2, 3, 4, 5])
# head = link.next
# tail = head.next.next
# a, b = Solution().reverse(head, tail)
# Link.each(b)
